#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>


using namespace std;

class Solution {
public:
    
    string sortString(string s) {
        
        map<char, int> M;
        for (int i = 0; i < s.size(); i++) {
            if (M.find(s[i])==M.end()) {
                M.insert(make_pair(s[i], 1));
            }
            else {
                ++M[s[i]];
            }
        }
        
        string sum = "";
        bool status = true;
        while (true) {
            int t = 0;
            if (status == true) {
                for (map<char, int>::iterator i = M.begin(); i != M.end(); i++) {
                    if (i->second > 0) {
                        sum += i->first;
                        t = 1;
                    }
                    (i->second)--;
                }
                status = false;
            }
            else {
                for (map<char, int>::reverse_iterator i = M.rbegin(); i != M.rend(); i++) {
                    if (i->second > 0) {
                        sum += i->first;
                        t = 1;
                    }
                    (i->second)--;
                }
                status = true;
            }
            if (t == 0) {
                break;
            }

       
        }
        return sum;

        
    }
};
//
//int main() {
//    string s = "ggggggg";
//    Solution S;
//    string sum =  S.sortString(s);
//    cout << sum << endl;
//    return 0;
//
//} 